package com.study.webapp.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 
 * @author admin
 *
 *         2018年12月4日
 */
public class Leet_21 {

	public static void main(String[] args) {
		ListNode l1 = new ListNode(1);
		ListNode l2 = new ListNode(1);
		ListNode a = new ListNode(2);
		ListNode b = new ListNode(3);
		ListNode c = new ListNode(4);
		a.next = c;
		l1.next = a;
		b.next = c;
		l2.next = b;
		ListNode l = getListNode(l1, l2);
		// ListNode l = getListNode(l1 = null, l2 = null);
		if (l != null) {
			ListNode p = l;
			while (p.next != null) {
				System.out.println(p.val);
				p = p.next;
			}
			System.out.println(p.val);
		}

	}

	public static ListNode getListNode(ListNode l1, ListNode l2) {
		if (l1 == null && l2 == null) {
			return null;
		}
		List<Integer> list = new ArrayList<>();
		if (l1 != null) {
			list.add(l1.val);
			ListNode pp = l1;
			while (pp.next != null) {
				list.add(pp.next.val);
				pp = pp.next;
			}
		}
		if (l2 != null) {
			list.add(l2.val);
			ListNode qq = l2;
			while (qq.next != null) {
				list.add(qq.next.val);
				qq = qq.next;
			}
		}

		Collections.sort(list);
		ListNode l = new ListNode(list.get(0));
		ListNode p = l;
		for (Integer in : list) {
			ListNode q = new ListNode(in);
			p.next = q;
			p = p.next;
		}
		return l = l.next;
	}

}
